Epoch-based {Logging, Checkpointing, Index}
皆さん，初めまして．NTT SICの中園 (nikezono) です．
この記事では，前日にご紹介したLineairDBを実装するうえで用いたインメモリDBの最適化手法について解説します． ３つの最適化があり，それぞれ{Logging, Checkpointing, Index}についての話になります．3日に分けようかと一瞬思いましたが，どれも小粒なのでまとめました．
記事の構成
1. インメモリDBの性能上の問題
1. a Logging
1. b Checkpointing
1. c Index
2. 銀の弾丸? Epoch Framework
3. Epoch Frameworkを使った最適化手法3種
3. a Epoch-based Distributed Logging
3. b Epoch-based Checkpointing
3. c Epoch-based ROWEX Index
前提
これから紹介する最適化手法は，どれもここ数年以内にのトップ国際会議の論文で紹介されたものです．
が，この最適化たちがうまく機能するためには，いくつかの前提があります：
shared-nothing かつ single-master．同じデータを複数のノードから更新はできない
DBのデータはメモリに乗り切る．インメモリDBでスワップアウトなし．
メニーコア環境(16コア以上くらい？）
つまり，インメモリDB特有の問題を解いています．ディスクベースのDBMSでは，この記事であげている問題がそもそもボトルネックにはならないので，問題ではありません．（ディスクI/Oの回数とレイテンシを減らすほうがずっと重要）．
1. インメモリDBの性能上の問題
1.a. Logging
LSNの利点と欠点
https://gyazo.com/89b0fb5d604e16db6ebe9b3d38cebbe6
一般的なDBMSでは，ログバッファは中央集権的な "Centralized Log Buffer" に対して書きこんでいきます．
これはリングバッファなりキューなりで実装されるので，ログバッファの内部には順序性があります．
いわゆるLSN (Log Sequence Number) などといったフォーマットで，明にログの中にこの順序が表現されることもあります．
これは非常に便利なものです．
リカバリの処理は，LSNの順番でバッファを反映させていけばよいので，シンプルです．
しかし，このような Centralized Log Bufferを用意すると，我々が前提とする環境ではこのBufferのアクセス権を得るためのLatchがかなり厳しいボトルネックになります． Distributed Loggingと失われる順序
https://i.gyazo.com/8e872ea103d9902e5854cea29f4864c3.png
そこで，各ワーカースレッドがそれぞれ自前のログバッファを持っておけば，完全に並列性が得られることになるので，インメモリDBにおいても性能は期待できるようになります．しかし，このアプローチも問題があり，LSNのようなログの順序関係が手に入らないので，コミットをどう返せばよいのか/リカバリをどの順序で適用すればいいのか，がわかりません．
※ マニア向けの注釈: ここでは「ログ永続化前にLockを解放する」すなわち Early Lock Releaseと呼ばれる技法を採用しているという前提を置いています．ログに VersionOrderを反映させることができるCC手法であればリカバリ処理に問題はありません．ただ，コミットを返す順序は，他のワーカーのログを読みに行かないとわかりません． 1.b. Checkpointing
チェックポイントを取る上で問題になるのが Point of Consistencyをとることです．
チェックポイントイメージは，
すべてのKey/Valueのデータが含まれていて，
ある任意の時間 (point) でデータベースを完全に止めた際のスナップショットと同じもの (consistent)
である必要があります．これを実現する方法は，ディスクベースのDBMSだと簡単なのですが，インメモリDBだと難易度が上がります．
シンプルで強力，Fuzzy Checkpointing
https://gyazo.com/9c1a5049d387de78931c8fff30c5331f
1. begin_checkpoint というレコードを書く．
2. ディスク上のページをコピーしていく．
この際，他のワーカーの挙動は止めない．そのため，inconsistent なイメージが出来上がる．
例えば，未コミットのトランザクションの書き込みが反映されていたり
例えば，コミット済みのトランザクションの書き込みが一部しか反映されていなかったり
3. end_checkpoint というレコードを書く．
リカバリ時の挙動は以下です:
1. begin < t < end であるような(つまりチェックポイントと並行で走っていた)トランザクション $ tのログを集める．
2. すべての変更を inconsistent imageに適用する．もしくは，すべての変更を破棄する．
3. 前者なら begin 時点の， 後者なら end 時点の point of consistency が保証される．
最悪の場合ジャイアントロックが必要なインメモリDBのCheckpointing
https://gyazo.com/bf080a2bc03a9c6d2cfa9b649e249588
インメモリDBだと，Checkpointingはなかなか困難です．以下の理由がぱっと挙げられます：
ディスク上に永続化されたページがないので，メモリ上からのフルスキャンになる
(Fuzzy Checkpointingを使わない場合) Read Lockを取ってフルスキャンしないと， consistent imageにならない．
それってつまりジャイアントロックになるのでは・・・
ディスクベースのDBMSならば，各ページを触りに行く際の細かい Latch だけで済んだのが，インメモリDBだと Lockと同じセマンティクスのものを使う必要がある，というのが問題のポイントです． (FYI: ロックとラッチ) # マニア向けの注釈: Value (Physical) ログをコンパクションする形でチェックポイントを作るアプローチもあるかと思いますが，ここでは扱っていません．試したことはありませんが，Distributed Loggingと組み合わせた場合，Thread-Local Log Bufferの縛りから，各ワーカースレッドにコンパクションを行わせる必要があるのが性能上難しそうです．
1.c. Index
Indexはそれ自体，実装が難しいものですが，並行インデックスを実装するとなるとさらに難易度が跳ね上がります．
この責務がまた，インメモリDBにおいては性能面で泣き所になります．
Indexと別建てできるPredicate Locking
https://gyazo.com/4ff9eb14e35fbb26581849b2acc33f51
例えば上図では，Worker 1と2が y というデータをInsertしたりDeleteしたりしています．
Worker 3 が SELECT * WHERE 'a' < key < 'z' というようなPredicateでReadを行った場合でも，このPredicate Lock Tableを見てやれば，衝突していることがわかるので，Wait/AbortすることでPhantomを回避できます．
実装もメンテも難しい，並行インデックス
https://i.gyazo.com/96708e8a860d7f6121c24f568dc98926.png
Predicate Lockingは実装もアイデアも簡単なのですが，全Workerが同じLock Tableを操作するという点で並列性が低いです．
もっと細粒度にPhantomを防ぐアプローチとして，Next-Key Lockingという手法があります．これはインメモリDBに限ったアイデアではありませんが，Predicate Lockingより（一般的に）高速です． これは，並行インデックス（たとえば B+ Tree) の線形リストを操作するとき，操作したいエントリと，その「次のエントリへのポインタ」のロックを取るアプローチです．別名Gap Lockともいいます．例えば，「a-zを読みたいトランザクションが，xを読んでいるときにyを挿入され，しかし気づかずにzに移動してしまった` 」といったケースを防ぐことができます． ただ，このアプローチは性能は悪くないのですが，実装が非常に難しい，とにかく難しいという問題があります．
マルチスレッドで B+Treeを操作して，split/mergeを考慮しながら，ポインタにもロックを取れるようにする....と考えるととてもしんどいです．(個人的に)
2. 銀の弾丸？ Epoch Framework
ここまでに挙げたインメモリDBの問題を，すべて解決可能？なアプローチがあります．
Microsoft ResearchのFASTERという論文ならびに関連論文でそう呼ばれています． https://i.gyazo.com/0c9049da23bfbf236a575bbe569022f6.png
Epoch Frameworkの基本的な動作は以下です．
トランザクションはすべて時間でいずれかの epoch $ e に属する
Epochは一定時間が経過したあとで “$ e-1に属するTxnsが全て終了” することで進行する
-> ある epoch $ e において，$ e-2 に属するActive Txns は存在しない
同一epochのトランザクションは，全て同じタイミングでCommitされる
-> 電源断や障害が発生した場合は，まとめてabort
このEpoch Frameworkを使うと，ある程度ルーズながら，並行処理で必要な “順序” が得られます．
すなわち，
$ e-2に属するトランザクションより， $ e-1に属するトランザクションのほうが「後」に起こったことは分かる
といった具合です．この”順序”を用いることで，全トランザクションにタイムスタンプを振るよりもリーズナブルに，タイムスタンプを振っていなければできなかったような最適化が可能となります．
3. Epoch Frameworkを使った最適化手法3種
3. a Epoch-based Distributed Logging
https://i.gyazo.com/4a312d6fc8293c14b40df0651a4d43a1.png
先程述べた "Distributed Logging, Commitを返す順番がわからない" 問題も，これで解決できます．
本来であれば「自分が読んだversionがすべてログ永続化され，Committedになったあとでしか」Commitできないので，他のワーカースレッドのトランザクションやログの進捗状況を見に行かなければなりませんが，その必要がなくなります．
たとえば， $ eのトランザクションが あるversion $ x_kを読んだとして，
$ t_kが同一Epochに属しているなら，同時にCommitするか一緒にAbortするかのどちらかなので，とりあえずログを書いて去ってしまえばよい
-> ユーザには "pre" commitを返し， epochが進行した際に改めて "まとめてcommitされた"ことを返す
$ t_kが他のEpochに属しているなら，Commitを返す順番のための "順序"はわかるので，そのとおりにcommitすればよい
# マニア向け注釈: トランザクションがどのEpochに属するかを決定するタイミングが早すぎると，「自分より後のEpochの書いたversionを読んでしまう」ことが起こりえます．これはAnomalyになるので，abortするなりpreventionするなりが必要です． 3. b Epoch-based Checkpointing
https://i.gyazo.com/ee4cd4c14d1c0acf1c43674e76be4f70.png
ワーカーとのロック競合に耐えながらフルスキャンすることが必要と考えられていたCheckpointingも，Epochを使うとわりかし問題をシンプルにできます．
たとえば， 近年の論文(CPR,CALC)で提案されている手法では，以下の手続きをとっています． インメモリDBのバッファ(Value)を，ひとつのKeyにつき２つ用意する．
ひとつは Live Image で，ワーカースレッドが更新する．
もうひとつは Stable Image で， チェックポイント用のもの．
Checkpoint Epoch を一定Epochごとに選出し，これに属するトランザクションが Stable Image を更新していく．
Checkpoint スレッドは， この Checkpoint Epoch が終了したあとで，このStable Imagesをフルスキャンする．
Checkpointスレッドの読み出し操作はワーカースレッドを邪魔しないので，ロックが必要ない．
Stable Image は，Checkpoint Epoch が終了した時点での Point of Consistencyが担保されているので，Fuzzy Checkpointingのような仕組みも必要ない．
LineairDBには，CPRという論文の実装をベースに，さらに少し最適化をした手法が実装されています． 以下の永続化ポリシーが選択できます：
ログのファイルサイズに制限がありません．チェックポイントのためのStable Imagesがないので省メモリです．
WALとCheckpointingを用いる Full Durability ログのファイルサイズをBoundedにできます．リカバリも高速です．
Checkpointingのみを用いるCPR Consistency
最新CheckpointのPoint of Consistencyまでを保証します．
それ以降のトランザクションは，コミットを返していても永続化されていない可能性があります．
RedisのAppend Only Files (AOF) に近い使用感になっています． WALを使わず，一定EpochごとにしかディスクI/Oを発行しない分，高速です．
3. c Epoch-based ROWEX Index
(※ このSection，draftなので以後加筆します...) #WIP https://i.gyazo.com/6299ded4ad61342bc2acffb2dea5b552.png
ROWEXとは，
Writerは変更したいデータをCASで一括変更する
ReaderはロックもValidationもしない
という排他制御のやり方で，OCCなどとも趣が異なるものです． 例えば，LineairDBでは，ROWEX Index という仕組みを導入しています．
1. 並行インデックスの実装は難しいので，やらない
2. Predicate Lockは，Predicate Lock Tableの管理が重たいので，やはりやらない
3. Indexは常にRead-Onlyで， ROWEXによってEpochごとに更新される
4. トランザクションは，Predicate (WHERE句) を用いるたびに，Read-Only Indexからスキャンする
5. Phantomを防ぐために，「このEpochでInsert/DeleteされたKey」のを保存しておく
このリストを使ってEpochごとにRead-only indexを更新していく．
このリストにすでにあるKeyをInsert/Deleteするトランザクションは，Abortする
つまり，同じKeyは同じEpochで高々１回しかInsert/Deleteできない
この機能によって，面倒な並行プログラミングをある程度省略して，Epochごとにロックのいらない Read-OnlyなIndexを更新する，という単純な実装とReadの高速性を得ています．
# マニア向け注釈: 実際には ROWEXはKeyのみのソート済み配列で充分です．これをEpoch数分用意して，$ eのトランザクションには $ e-1のIndexを読ませます． GCはRCU-QSBRです． # これは現在 (2020/12/17時点で) LineairDBには開発中の機能となります．
Epoch Frameworkの問題点
一瞬，銀の弾丸のように思えるEpoch Frameworkですが，既知の問題がいくつかあります．
Commitまでの平均レイテンシが伸びる
Epochの進行条件を再掲すると，"一定時間経過 + Epochから全Workerが退出 + Epochの全トランザクションがpre-committed"です．このために，かなり短いトランザクションでも一定のレイテンシがかかることがあります．例えば，SiloではEpochのサイズを40msに指定しているため，とても単純なトランザクションでも，Epochのはじめのほうに実行されてしまった場合，最低40msはコミットまで待つことになります． Long Transactionが入ると Epochの進行が止まる
これは一つ前の問題をよりオーバーにしたものです．"Epochの全トランザクションがpre-committed" までEpochが進行できないということは，うっかり手が滑って SELECT * FROM table とか，indexのないテーブルを全部outer joinするようなクエリとか，そういう Long Transactionを発行してしまうと，現在実行中の（そしてこれから実行される）トランザクションすべてが，このLong Transactionが終わるまでコミットできなくなります． 多種多様なクエリを含むワークロードでは，まだまだ課題の多い手法といえるのがEpoch Frameworkです．
おわりに
NTT SICでは，トランザクショナルKVS である LineairDBをOSSとして公開しています． 他のデータベースでいわゆるストレージエンジンと呼ばれている InnoDB, TiKV, LevelDB などに近い思想で実装しており，
他のより大きいデータベースの一部として動作すること
モバイル開発や組み込みなどでの利用
を想定しています．ここで挙げたEpoch Frameworkと，関連する最適化のように，高速化のための知見を積極的に取り入れたソフトウェアにしていきたいと思っています．
LineairDBはまだversion 1.0 未満のソフトウェアで，コミッタも私一人 (2020/12/17時点) ですが，パッチ投稿やテスト，ベンチマーク，実験など，どのような形でも関わっていただけるcontributorを常に募集しています．ぜひお気軽にどうぞ！